import java.util.*;

class Solution {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    int m, n;

    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size();
        n = forest.get(0).size();
        ArrayList<int[]> tmp=new ArrayList<>();
        for(int i=0;i<m;i++){
            for (int j = 0; j < n; j++) {
                int heigh=forest.get(i).get(j);
                if(heigh>1) tmp.add(new int[]{heigh,i,j});
            }
        }
        tmp.sort((a,b)->(a[0]-b[0]));
        int count=0;
        int x=0;
        int y=0;

        for(int[] arr:tmp){
            int step=bfs(forest,arr,x,y);
            if(step==-1) return -1;
            count+=step;
            forest.get(x).set(y,1);
            x=arr[1];
            y=arr[2];

        }
        return count;

    }

    public int bfs(List<List<Integer>> forest,int[] arr,int a,int b){
        if(a==arr[1]&&b==arr[2]) return 0; //注意判断第一个位置是否为要砍的地方
        boolean[][] vis=new boolean[m][n];
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{a,b});
        vis[a][b]=true;
        int count=0;
        while(!q.isEmpty()){
            int sz=q.size();
            for(int j=0;j<sz;j++){
                int[] t=q.poll();
                int x=t[0];
                int y=t[1];
                for(int i=0;i<4;i++){
                    int nx=dx[i]+x;
                    int ny=dy[i]+y;
                    if(nx>=0&&nx<m&&ny>=0&&ny<n&&!vis[nx][ny]&&forest.get(nx).get(ny)!=0){
                        if(nx==arr[1]&&ny==arr[2]) return count+1;
                        vis[nx][ny]=true;
                        q.add(new int[]{nx,ny});
                    }

                }
            }
            count++;
        }
        return -1;

    }


}



class Solution1 {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    boolean[][] vis;
    public int numEnclaves(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        vis=new boolean[m][n];
        Queue<int[]> q=new LinkedList<>();

        for(int i=0;i<m;i++){
            if(grid[i][n-1]==1){
                q.add(new int[]{i,n-1});
                vis[i][n-1]=true;

            }
            if(grid[i][0]==1){
                q.add(new int[]{i,0});
                vis[i][0]=true;

            }

        }

        for(int i=1;i<n-1;i++){
            if(grid[m-1][i]==1){
                q.add(new int[]{m-1,i});
                vis[m-1][i]=true;
            }
            if(grid[0][i]==1){
                q.add(new int[]{0,i});
                vis[0][i]=true;
            }

        }
        int count=0;
        bfs(grid,q);
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(grid[i][j]==1&&!vis[i][j]) count++;
            }

        return count;


    }

    public void bfs(int[][] grid,Queue<int[]> q){
        while(!q.isEmpty()){
            int[] arr=q.poll();
            int x=arr[0];
            int y=arr[1];
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1&&!vis[nx][ny]){
                    q.add(new int[]{nx,ny});
                    vis[nx][ny]=true;
                }
            }
        }

    }
}



class Solution2 {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    int[][] ret;
    public int[][] highestPeak(int[][] isWater) {
        m=isWater.length;
        n=isWater[0].length;
        ret=new int[m][n];
        Queue<int[]> q=new LinkedList<>();

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(isWater[i][j]==1){
                    q.add(new int[]{i,j});
                }else{
                    ret[i][j]=-1;
                }
            }

        }

        bfs(isWater,q);
        return ret;



    }



    public void bfs(int[][] grid,Queue<int[]> q){
        while(!q.isEmpty()){
            int[] arr=q.poll();
            int x=arr[0];
            int y=arr[1];
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&ret[nx][ny]==-1){
                    q.add(new int[]{nx,ny});
                    ret[nx][ny]=ret[x][y]+1;
                }
            }

        }

    }
}






